package william.string;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhangShenao
 * @date 2024/3/2
 * @description <a href="https://leetcode.cn/problems/reverse-vowels-of-a-string/description/">...</a>
 */
public class Leetcode345_反转字符串中的元音字母 {
    //构造元音字母表
    private static final Set<Character> vowels = new HashSet<>();

    static {
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
    }

    /**
     * 采用指针对撞法
     * 同时从首、尾两端遍历字符串,找到元音字母,进行交换
     * <p>
     * 时间复杂度O(N) 只遍历字符串一次
     * 空间复杂度O(N) 因为字符串不可变,需要将字符串先转换成字符数组
     */
    public String reverseVowels(String s) {
        //边界条件校验
        if (s == null || s.length() < 2) {
            return s;
        }

        //采用指针对撞法,同时从首、尾两端遍历字符串,找到元音字母,进行交换
        char[] chars = s.toCharArray();
        int l = 0;
        int r = chars.length - 1;
        while (l < r) {  //当l==r时无需交换
            char c1 = chars[l];
            char c2 = chars[r];

            //跳过非元音字母
            if (!vowels.contains(c1)) {
                l++;
                continue;
            }
            if (!vowels.contains(c2)) {
                r--;
                continue;
            }

            //将元音字母进行交换
            swap(chars, l++, r--);
        }

        //将反转后的字符数组转换成字符串返回
        return new String(chars);
    }

    /**
     * 将数组i,j两个位置的元素交换
     */
    private void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }
}
